A computer system and an operating system thereof may employ capabilities to represent, address and grant access to objects or resources, such as regions of memory. A capability is a token of authority that points to a range of memory addresses and includes a set of permissions indicating operations, such as read, write and execute etc., for which the capability grants permission. For example, a capability may include a base and a length which together define an area of memory and number of permission bits which indicate whether an operation corresponding to the permission bit is allowed or not.
When an area of memory is allocated to a process, a capability may be created by the operating system kernel. This original capability may cover a relatively large region of memory. Based on this original capability, a number of derived capabilities may be created, each derived capability pointing to a sub-set of memory addresses within the range of memory addresses governed by the original capability. The derived capabilities may be used to access particular pieces of data or for other purposes associated with the process. As a result, a process may create a large number of derived capabilities, which are based on an original capability.
When the memory resource is freed up for reallocation, the corresponding capabilities, both the original and derived ones, may be revoked and deleted. One approach is to keep some sort of linked list or chains of pointers to track all the derived capabilities so that they can be found and revoked. However, this makes revocation a costly and complex operation.